import java.util.LinkedList;

/* UNIVERSIDADE FEDERAL DE CAMPINA GRANDE - UFCG
 * Disciplina: Laboratorio de Estrutura de Dados
 * Professor: Marco Aurelio Spohn
 * Alunos: Alexandre Sales Vasconcelos       Mat.: 20621146
 * Atividade 13
 */

/**
 * Classe que implementa o algoritmo Dijkstra.
 *
 * @version 1.0 2008/07/25
 * @author Alexandre Sales Vasconcelos
 * @see <a href="http://lab.eda.ufcg.googlepages.com/grafosmenorcaminho"> Atividade 13</a>
 */
public class Dijkstra {
	//Definicao de valores Fixo
	final int NAOLOCALIZADO = -1;

	LinkedList<Aresta> arestas;

	LinkedList<Vertice> grafos;

	Vertice raiz;


	/**
	 * Construtor da classe Dijkstra
	 * 
	 * @param string com a entrada de dados
	 */
	public Dijkstra(String string) {
		

		grafos = new LinkedList<Vertice>();
		arestas = new LinkedList<Aresta>();
		
		String[] entrada = string.split(" ");
		int chave1;
		int chave2;
		int peso;
		int posicaoChave1;
		int posicaoChave2;
		Vertice vertice1;
		Vertice vertice2;
		
		raiz = new Vertice(Integer.parseInt(entrada[0]));
		grafos.add(raiz);

		
		
		for (int i = 1; i < entrada.length; i = i+3) {
			chave1 = Integer.parseInt(entrada[i]);
			chave2 = Integer.parseInt(entrada[i+1]);
			peso = Integer.parseInt(entrada[i+2]);
			posicaoChave1 = seachKey(chave1);
			posicaoChave2 = seachKey(chave2);
			 // verifica se os vertices ja estao nas lista encadadas
			if (posicaoChave1 == NAOLOCALIZADO && posicaoChave2 == NAOLOCALIZADO) { // se vertice 1 e 2 nao existir
				vertice1 = new Vertice(chave1);
				vertice2 = new Vertice(chave2);
				grafos.add(vertice1);
				grafos.add(vertice2);
				arestas.add(new Aresta(vertice1, vertice2, peso));
			} else if (posicaoChave1 == NAOLOCALIZADO && posicaoChave2 != NAOLOCALIZADO) { // se so o vertice 1 existir
				vertice1 = new Vertice(chave1);
				vertice2 = grafos.get(posicaoChave2);
				grafos.add(vertice1);
				arestas.add(new Aresta(vertice1, vertice2, peso));
			} else if (posicaoChave1 != NAOLOCALIZADO && posicaoChave2 == NAOLOCALIZADO) { // se so o vertice 2 exixtir
				vertice1 = grafos.get(posicaoChave1);
				vertice2 = new Vertice(chave2);
				grafos.add(vertice2);
				arestas.add(new Aresta(vertice1, vertice2, peso));
			} else if (posicaoChave1 != NAOLOCALIZADO && posicaoChave2 != NAOLOCALIZADO) { // se os 2 existirem
				vertice1 = grafos.get(posicaoChave1);
				vertice2 = grafos.get(posicaoChave2);
				arestas.add(new Aresta(vertice1, vertice2, peso));
			}
		}
		
		menorCaminho();
		grafos = BubbleSort(grafos);
		
	}

	/**
	 *  Metodo para encontra o menor caminho
	 */
	private void menorCaminho() {
		if (!origens(raiz).isEmpty()) {
			
			raiz.caminho = 0;
			
			LinkedList<Vertice> S = new LinkedList<Vertice>();

			LinkedList<Vertice> Q = new LinkedList<Vertice>();
			Q.addAll(grafos);
			
			while (!Q.isEmpty()) {
				Vertice u = extractMin(Q);
				S.add(u);
				for (int i = 0; i < origens(u).size(); i++) {
					Aresta aux = origens(u).get(i);
					if (u.caminho + aux.peso < aux.destino.caminho && u.caminho + aux.peso > 0) {
						aux.destino.caminho = u.caminho + aux.peso;
					}
				}
			}
		}
	}

	/**
	 * Metodo que ordena o grafo pelo algortimo BubbleSort.
	 * 
	 * @param grafo a ser ordenado.
	 * @return grafo ja ordenado.
	 */
	private LinkedList<Vertice> BubbleSort(LinkedList<Vertice> grafo) {
		Vertice vertice = null;
		boolean swap;
		
		for (int i = 1; i < grafo.size(); i++) {
			swap = false;
			for (int j = grafo.size()-1; j >= i; j--) {
				if (grafo.get(j-1)!=null && grafo.get(j)!=null && grafo.get(j-1).chave > grafo.get(j).chave) {
					vertice = grafo.get(j);
					grafo.set(j, grafo.get(j-1));
					grafo.set(j-1, vertice);
					swap = true;
				}
			}
			if (!swap) break;

		}
		
		return grafo;
	}

	/**
	 * Metodo que verifica se o vertice é origem da aresta.
	 * 
	 * @param u vertice a ser verificado.
	 * @return uma linkedlist com os vertices de origem.
	 */
	private LinkedList<Aresta> origens(Vertice u) {
		LinkedList<Aresta> origens = new LinkedList<Aresta>();
		for (int i = 0; i < arestas.size(); i++) {
			if (arestas.get(i).origem == u) {
				origens.add(arestas.get(i));
			}
		}
		return origens;
	}

	/**
	 * Metodo que estra o menor caminho do grafos
	 * 
	 * @param Q
	 * @return
	 */
	private Vertice extractMin(LinkedList<Vertice> Q) {
		int menor = 0;
		for (int i = 1; i < Q.size(); i++) {
			if (Q.get(i).caminho < Q.get(menor).caminho) {
				menor = i;
			}
		}
		return Q.remove(menor);
	}
	
	/**
	 * Metodo que procura se ja existe alguma lista com essa chave, caso afirmativo retorna qual sua
	 * posicao na linkedlist.
	 * 
	 * @param chave a ser pesquisada na lista.
	 * @return inteiro com a posicao localizada (-1 caso na tenha localizado).
	 */
	private int seachKey(int chave) {
		for (int i = 0; i < grafos.size(); i++) {
			if (grafos.get(i).chave == chave) {
				return i;
			}
		}
		return NAOLOCALIZADO;
	}

	/**
	 * Metodo que imprime a lista formatado.
	 * 
	 * @return String com os elementos da lista formatado.
	 */
	public String toString() {
		String saida = "";
		String temp;
		for (int i = 0; i < grafos.size(); i++) {
			Vertice vertice = grafos.get(i);
			if (vertice != raiz) {
				if (vertice.caminho == Integer.MAX_VALUE) {
					temp = "X";
				} else {
					temp = vertice.caminho + "";
				}
				saida += temp + ", ";
			}
		}
		return saida.substring(0, saida.length() - 2);
	}

}